import math
import random

def calc_dist(p1, p2):
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))

def find_nearest(pt, centers):
    dists = [calc_dist(pt, c) for c in centers]
    return dists.index(min(dists))

def kmeans(data, k, eps=1e-4, max_iter=100):
    centers = random.sample(data, k)
    history = []  

    for i in range(max_iter):

        labels = [find_nearest(pt, centers) for pt in data]

        error = sum(calc_dist(data[idx], centers[label]) ** 2 for idx, label in enumerate(labels))

        new_centers = []
        for j in range(k):
            group = [data[idx] for idx, label in enumerate(labels) if label == j]
            if group:
                new_center = [sum(dim) / len(group) for dim in zip(*group)]
            else:
                new_center = random.choice(data)
            new_centers.append(new_center)

        history.append({
            'iteration': i + 1,
            'centers': centers.copy(),
            'error': error,
            'labels': labels.copy()
        })


        max_move = max(calc_dist(old, new) for old, new in zip(centers, new_centers))
        if max_move < eps:
            print(f"第{i + 1}轮后收敛，最大移动距离: {max_move:.6f}")
            break

        centers = new_centers
        print(f"第{i + 1}轮完成，误差: {error:.2f}，最大移动: {max_move:.4f}")

    return centers, labels, history


def evaluate_clustering(data, centers, labels):
    compactness = []
    for j in range(len(centers)):
        cluster_points = [data[idx] for idx, label in enumerate(labels) if label == j]
        if cluster_points:
            avg_dist = sum(calc_dist(pt, centers[j]) for pt in cluster_points) / len(cluster_points)
            compactness.append(avg_dist)
        else:
            compactness.append(0)

    total_error = sum(calc_dist(data[idx], centers[label]) ** 2 for idx, label in enumerate(labels))

    return {
        'total_error': total_error,
        'compactness': compactness,
        'cluster_sizes': [labels.count(j) for j in range(len(centers))]
    }

if __name__ == "__main__":

    random.seed(42)
    data = []
    for center in [(2, 2), (6, 6), (2, 6)]:
        data += [[random.gauss(center[0], 0.5), random.gauss(center[1], 0.5)] for _ in range(50)]

    print(f"数据点总数: {len(data)}")

    centers, labels, history = kmeans(data, 3)

    print("\n最终中心点:")
    for i, c in enumerate(centers):
        print(f"中心{i}: ({c[0]:.2f}, {c[1]:.2f})")

    evaluation = evaluate_clustering(data, centers, labels)

    print(f"\n聚类评估:")
    print(f"总误差: {evaluation['total_error']:.2f}")
    print(f"每组点数: {evaluation['cluster_sizes']}")
    print(f"各聚类平均距离: {[f'{x:.2f}' for x in evaluation['compactness']]}")

    print(f"\n迭代历史 (共{len(history)}轮):")
    for i, record in enumerate(history[-3:]):
        print(f"第{record['iteration']}轮 - 误差: {record['error']:.2f}")